1. Field of Use
The present invention relates to data processing system and more particularly to queuing systems.
2. Related Art
A frequent activity in data processing systems is the enqueueing of a data item. Typically, these systems maintain many queues internally. Often, the queues correspond to waiting-lines of work to be done by the data processing system so that when an item is to be added to the queue, the queue system simply appends the item to the end of the queue and when an item is to be removed, the queue system removes the item from the front of the queue.
Sometimes the items in a queue system must be held in the queue in a particular order which is dependent upon a particular field or fields contained in the item. An example is where the queue system functions as a scheduler and represents the tasks to be executed by the data processing system. In such cases, each of the data items normally contains a field representing the priority of the task and the data items representing low priority tasks are enqueued after the data items representing higher priority tasks. To add such a low priority data item to the queue system, the simplest implementation requires that the queue insertion mechanism perform a sequential search of the queue beginning with the data item at the front of the queue system and examining each enqueued data item in turn until the insertion mechanism locates a data item having a priority which is the same or lower than the priority of the data item to be inserted into the queue system.
When the queue system contains many data items, the sequential search can require a substantial amount of time thereby detracting from the overall efficiency of the data processing system. In general, the search time grows linearly with the number of data items in the queue system.
A queue is generally represented in a data processing system by a data structure to implement the queue itself along with multiple data structures for each of the data items. That is, each data item contains fields for its data in addition to extra fields for implementing the queue structure. Generally, a simple queue implements the queue structure as a single data item which corresponds to the memory address of the first queued data item and each data item has one field dedicated to the queue structure which contains the memory address of the next data item in the queue.
Alternative queue data structures are well known to those skilled in the art. A variation of the simple queue structure is the double linked list organization which contains two fields per data item, one field containing the memory address of the next enqueued data item and the other field containing the memory address of the preceding data item in the queue. This organization simplifies the addition and removal of data items from the middle of the queue by being able to search for data items in either a forward or backward direction. Thus, while a simple ordered queue has very efficient insertion and removal of data items, there is still a substantial search burden when the size of the queue is substantial.
Another known queue data structure is one representing the ordered queue as a tree-shaped data structure with the branching of the tree being dependent on the value of the key field or fields so that search time can grow as the logarithm base two of the number of items in the tree provided that the tree is balanced. Unfortunately, maintaining the tree in a balanced state is expensive when there are frequent additions and removals of data items.
Another known queue data structure is a "skip list" which holds multiple copies of a data item in multiple queues. The lowest level queue contains all of the items to be enqueued while the higher level queues hold just a subset of items chosen at random from the immediate lower queue. In this arrangement, a search proceeds from the highest level queue, migrating down to the next lower level queue when a pseudo match is obtained. This queue structure is less expensive to maintain than a balanced tree queue structure and provides probabilistic speedups in search time. But, the structure pays a penalty in terms of memory space (i.e. multiple copies of the data items are needed) and its insertion and deletion mechanisms are more expensive as compared to the simple queue structure.
Accordingly, it is a primary object of the present invention to provide an efficient, probabilistic search mechanism for ordered queues.
It is a further object of the present invention to provide an efficient search mechanism which provides for efficient insertion and removal of data items.